package binaryTree;

import java.util.Arrays;
import java.util.HashMap;


/**利用带空的先序遍历结果或不带空的先序和中序遍历结果建立二叉树
 * 
 * */
public class BinaryTree<AnyType> {
	public AnyType[] tmp;
	public AnyType[] tmp1;
	public HashMap<AnyType,Integer> mapIndex=new HashMap<AnyType,Integer>();
	
	/**根节点*/
	private BTNode<AnyType> rootNode;
	int i=0;
	int count=0;
	public BinaryTree(){
		rootNode=null;
	}
	public BinaryTree(AnyType rootData){
		rootNode.setData(rootData);
		rootNode.setLeftChild(null);
		rootNode.setRightChild(null);
	}
	public BinaryTree(BTNode<AnyType> t){
		this.rootNode=t;
	}
	
	/**得到根节点*/
	public BTNode<AnyType> getNode(){
		return rootNode;
	}
	/**设置根节点*/
	public void setNode(BTNode<AnyType> rootNode){
		this.rootNode=rootNode;
	}
	/**返回节点个数
	 * */
	public int countNode(){
		return countNode(rootNode);
	}
	
	private int countNode(BTNode<AnyType> rootNode){
		int m=0,n=0;
		int i=0;
		if(rootNode==null){
			return 0;
		}
		m=countNode(rootNode.getLeftChild());
		n=countNode(rootNode.getRightChild());
		return m+n+1;
	}
	
	/**利用带空的先序遍历结果创建二叉树
	 * */
	public BTNode<AnyType> createBTByPreOrder(AnyType[] preOrder){
		BTNode rootNode=null;
		if(i>=preOrder.length){
			throw new  ArrayIndexOutOfBoundsException();
		}
		AnyType data=preOrder[i++];
		if(data!=null){
			rootNode=new BTNode<AnyType>(data);
			rootNode.setLeftChild(createBTByPreOrder(preOrder));
			rootNode.setRightChild(createBTByPreOrder(preOrder));
		}
		return rootNode;
	}
	
	/**利用不带空的先序和中序遍历结果创建二叉树
	 * offset=0
	 * */
	
	public BTNode<AnyType> createBTByPreAndInOrder(AnyType[] preOrder,AnyType inOrder[],int offset){
		int i;
		tmp=Arrays.copyOfRange(preOrder, 0, preOrder.length);
		tmp1=Arrays.copyOfRange(preOrder, 0, preOrder.length);
		
		//将中序遍历序列元素标记位置号
		
		for(i=0;i<preOrder.length;i++){
			mapIndex.put(preOrder[i], i);
		}
		
		BTNode rootNode=createBTByPreAndInOrder(preOrder,i,offset);
		
		return rootNode;
	}
	public BTNode<AnyType> createBTByPreAndInOrder(AnyType[] preOrder,int n,int offset){
		
		if(0==n){
			return null;
		}
		AnyType rootVal=preOrder[0];
		int i=mapIndex.get(rootVal)-offset;
		BTNode<AnyType> root = new BTNode<AnyType>(rootVal);
		tmp = Arrays.copyOfRange(tmp, 1, tmp.length);
		root.setLeftChild(createBTByPreAndInOrder(tmp,i,offset));
		
		tmp1=Arrays.copyOfRange(tmp1, i+1, tmp1.length);
		root.setRightChild(createBTByPreAndInOrder(tmp1,n-i-1,offset+i+1));
		
		return root;
	}
	
	/**先序遍历*/
	public void preOrder(BTNode<AnyType> t){
		if(t!=null){
			/**访问根节点*/
			count++;
			System.out.println(t.getData());
			/**遍历左子树*/
			preOrder(t.getLeftChild());
			/**遍历右子树*/
			preOrder(t.getRightChild());
		}
	}
	
	//测试利用不带空的先序和中序遍历结果创建二叉树
	public static void main(String[] args){
		int[] pre={7, 10, 4, 3, 1, 2, 8, 11};
		Integer[] p=new Integer[pre.length];
		for(int i=0;i<pre.length;i++){
			p[i]=pre[i];
		}
		int[] in={4, 10, 3, 1, 7, 11, 8, 2};
		Integer[] q=new Integer[in.length];
		for(int i=0;i<in.length;i++){
			q[i]=in[i];
		}
		BinaryTree<Integer> b=new BinaryTree<Integer>();
		b.setNode(b.createBTByPreAndInOrder(p,q,0));
		b.preOrder(b.rootNode);
		
	}
	
}
